COMMENT ⊗   VALID 00010 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.REQUIRE "206MAC.PUB[206,LSP]" source_file
C00003 00003	.hd206 FALL 1979
C00006 00004	.bb Proving
C00009 00005	.bb Formal systems
C00011 00006	.bb Compiling
C00013 00007	.bb Games
C00014 00008	.bb AIish programs
C00015 00009	.bb  Data manipulating programs.
C00017 00010	.bb Some previous projects.
C00018 ENDMK
C⊗;
.REQUIRE "206MAC.PUB[206,LSP]" source_file;
.
.odd heading(,,{page}) ;
.even heading({page}, , ) ;
.
.LSPFONT
.basicops 
.
.allops
.itemmac 1;
.
.PORTION MAINPORTION
.hd206 FALL 1979
.PAGE ← 1
.cb TERM PROJECTS

	A term project is not required in order to pass CS206 or even to
get a grade of B if your homework and exams are good enough.  However, if
you wish to get some flavor of A then doing a good term project is necessary.
Term projects will be due on the day of the final exam.  Any term project
turned in ahead of time will be likely to get a more thorough reading.

	The term project is your opportunity to direct your attention
to and get experience in some area that interests you.   
It may be programming or theoretical or both.   A programming project
may be related to computing (a compiler), AI (game playing, problem
solving) other areas of computer science, or some unrelated area
in which you have interest and expertise.  A theoretical project
should relate to reasoning about LISP programs.   Some ideas are
given below.  Feel free to design your own project.  

	The write-up of your project is the main thing that will get
graded so it should be clear and carefully done.  It should include
a brief description of what you set out to do and what you accomplished.
If you write a progam, you should give a description of how it works
and why, including a description of the data structures it is acting
on and the basic operations on these structures.  The code
for the program should be included with brief comments in appropriate
places to guide the reader.  Some sample runs should also be included.

	Before putting a lot of work into your project, you should
outline carefully just what you plan to do and have this approved
by the instructor or the TA.   You are also encouraged to discuss
initial ideas before finalizing your plans.

.group		
.bb Proving

#. Develop and apply techniques for proving properties of programs
manipulating graphs.  The proofs should be fully formal, but also
natural and cleanly expressible.  Some particular problems to be
considered are formalizing abstractly the notions of graph, path,
component, etc.  Showing that a particular S-expression representation
of graphs satisfy the same properties as the abstract notion.  Developing
principles for proving that programs on graphs terminate.  Specifying
and proving correctness of some graph programs (list all nodes, find a
path from ⊗v1 to ⊗v2, find the shortest path, etc.	
[Remark:  for a term project you expected only to solve a select few of
these problems, not all of them.]

#.  Develop the theory of re-entrant list structures.  (see Chapter IV.)
Decide on a representation
of such structures as ordinary lists (say with pointers and labels).  Define
some primitive operations (for example: ⊗⊗car cdr cons point cut⊗).  Write programs
to go from one representation to the other.  Write an equality predicate in
for structures in your representation.   Work out an induction schema to
allow you to tell when programs on such structures will terminate.
Write some interesting programs on such structures and prove some facts
about them.

#.  Prove a moderate size "practical" program correct.  For example
a modest pattern matcher, unifier, or  simple production rule system
would be appropriate.
.apart

.group
.bb Formal systems

#. Write a proof checker for a simple formal system.   Some examples
of suitable formal systems are:
.skip
.begin preface 0 indent 8,8

##. Trigonometric expressions: using trig identities to prove expressions
equivalent.

##. Symbolic integration: using various standard tricks for manipulating
integrands into integrable form.

##. Propositional logic and a Hilbert or natural deduction style proof
system.
.skip
Some "bells and whistles" that you might consider adding to your system
include:
.skip
##. Implement some heuristics to search for proofs.

##. Implement some derived rules plus the ability to expand a deduction
using the derived rule into one consisting only of elementary steps.
.end
.apart

.group

.bb Compiling
.begin indent 0,4

#. Improve the LCOM4 compiler.  Some possibilities are to modify LCOM4 to:
.begin nofill indent 8,8

##. compile  ⊗label. 
##. handle the %3prog%1 and related features.
##. handle functions as arguments (as for ⊗mapcar) .
##. recognize iteration and compile it with loops.
##. produce more efficient arithmetic code.
##. compile additional features such as "while's" or "do's" etc..
.end

#. Write a data driven compiler for LISP.

#. Write a syntax directed compiler for LISP.   Perhaps several passes using
an intermediate language would be useful.  
.apart

.group

.bb Games

#. Write a program to play a game.  Some possible games are:
.begin nofill indent 8,8

##. 3-dimensional Tic Tac Toe (See forthcoming Chapter for 2-D version.)
##. Solitare
##. Mastermind
##. Otello
.end

    There are two key issues in programs to play games.  One is
the method used to prune the search for possible moves, the other
is developing good strategies of choosing moves.  These issues are
of course not independent from one another.

    Be sure to hold individual test runs to a few seconds.  It is easy to
use large amounts of computer time in such projects.  
.apart

.group

.bb AIish programs

#.  Write a program that generates form letters.  You should have
a particular class of user in mind, say a business, or political group.
It should deal with a variety of situations and the resulting letter
should depend in an interesting way on set of facts about recipient of letter.

#. A natural language program, for example a program that does
morphemic analysis of English.  You should have a clearly defined
class of words that can be analyzed by your program.
.apart

.group

.bb  Data manipulating programs.

#.  Write a program that does file cross referencing for some
interesting class of files.

#.  Answering questions about a data base of facts.
Assume you have a finite domain of objects and a data base
of facts about these objects.  For example assume that there is a given
collection of relations that apply to the objects and
all true instances of these relations are in the data base.
(The closed world assumption.)   Write a program that decides the
truth or falsity of any first order sentence built from  the given
relation symbols, variables and names of the objects.  An interesting
and useful extension is to allow a formula with one free variable
and have the program return one or more objects (if any) that satisfy
the formula.
.apart

.group

.bb Some previous projects.

#. Minimizing finite state machines

#. Digital Circuit design:  design representation of gates and
circuits.  Implement algorithms for optimizing circuit designs or layouts.

#. LALR parser

.end
.apart